
 class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        //使用快慢双指针 慢指针找到中点，快指针找到尾巴节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //从中间节点后面开始逆置链表 - 头插法
        ListNode newHead = slow.next;
        slow.next = null;
        ListNode cur = newHead.next;
        newHead.next = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = next;
        }
        //再合并链表
        cur = head;
        ListNode newCur = newHead;
        while(newCur != null){
            ListNode next = cur.next;
            ListNode newNext = newCur.next;
            cur.next = newCur;
            newCur.next = next;
            cur = next;
            newCur = newNext;
        }
    }
}